package 题目集.线段树or树状数组.树状数组;

//这是第二次写，理解的更加深刻，并且更加简洁

/**
 * https://leetcode.cn/problems/range-sum-query-mutable/description/
 */
public class ch01_模板 {
    private long[] tree;
    private int n;

    public ch01_模板(int n) {
        this.n = n;
        tree = new long[n + 1];
    }
    public void add(int i,long v){
        while (i <= n){
            tree[i] += v;
            i += lowbit(i);
        }
    }
    //如果有修改操作推荐再备份一个原数组，old从原数组中取
    public void update(int i,long v){
        long old = query(i) - query(i - 1);
        add(i,v-old);
    }
    //查询1~n的前缀和
    public long query(int n){
        long sum = 0;
        while (n > 0){
            sum += tree[n];
            n -= lowbit(n);
        }
        return sum;
    }
    public long range(int l,int r){
        return query(r) - query(l - 1);
    }

    private int lowbit(int x) {
        return x & -x;
    }
}
